| 翻訳と辞書 |
| Graph toughness ： ウィキペディア英語版 |
Graph toughness
In graph theory, toughness is a measure of the connectivity of a graph. A graph is said to be -tough for a given real number if, for every integer , cannot be split into different connected components by the removal of fewer than vertices. For instance, a graph is -tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum for which it is -tough; this is a finite number for all graphs except the complete graphs, which by convention have infinite toughness.
Graph toughness was first introduced by . Since then there has been extensive work by other mathematicians on toughness; the recent survey by lists 99 theorems and 162 papers on the subject.
==Examples==
Removing vertices from a path graph can split the remaining graph into as many as connected components. The maximum ratio of components to removed vertices is achieved by removing one vertex (from the interior of the path) and splitting it into two components. Therefore, paths are -tough. In contrast, removing vertices from a cycle graph leaves at most remaining connected components, and sometimes leaves exactly connected components, so a cycle is -tough.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Graph toughness」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|